package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @class Code75
 * @description 剑指 Offer 66. 构建乘积数组
 * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
 * 其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积,
 * 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 *
 *  
 *
 * 示例:
 *
 * 输入: [1,2,3,4,5]
 * 输出: [120,60,40,30,24]
 *  
 *
 * 提示：
 *
 * 所有元素乘积之和不会溢出 32 位整数
 * a.length <= 100000
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-20 8:24
 */
public class Code75 {
    public static void main(String[] args) {
        int[] a = new int[]{1,2,3,4,5};
        System.out.println(constructArr(a));
    }

    public static int[] constructArr(int[] a) {
        int[] dp1 = new int[a.length + 2];
        int[] dp2 = new int[a.length + 2];
        dp1[0] = 1;
        dp2[0] = 1;
        dp1[dp1.length - 1] = 1;
        dp2[dp2.length - 1] = 1;
        for (int i = 1; i < a.length + 1; i++) {
            dp1[i] = dp1[i - 1] * a[i - 1];
            dp2[a.length + 1 - i] = dp2[a.length + 2 - i] * a[a.length - i];
        }
        int[] res = new int[a.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = dp1[i] * dp2[i + 2];
        }
        return res;
    }

}
/*
动态规划
创建两个数组dp1[i] 代表前 i 个数的乘积
dp2[i] 代表后 i 个数的乘积
res[i] = dp1[i - 1] * dp2[i + 1]
 */